package Solutions

type gNode struct {
	id     int
	t      int
	child  []*gNode
	parent *gNode
}

func networkDelayTime(times [][]int, n int, k int) int {
	var distanceMap = make(map[int]map[int]int)
	for _, item := range times {
		if mp, ok := distanceMap[item[0]]; ok {
			mp[item[1]] = item[2]
		} else {
			distanceMap[item[0]] = map[int]int{
				item[1]: item[2],
			}
		}
	}
	var nodeMap = make(map[int]*gNode)
	var dfs func(node *gNode)
	rootNode := &gNode{
		id: k,
		t:  0,
	}
	nodeMap[k] = rootNode
	dfs = func(node *gNode) {
		childs := distanceMap[node.id]
		for id, distance := range childs {
			if child, ok := nodeMap[id]; ok {
				if child.t > node.t+distance {
					child.t = node.t + distance
					for i, v := range child.parent.child {
						if v == child {
							child.parent.child[i] = nil
						}
					}
					child.parent = node
					dfs(child)
					node.child = append(node.child, child)
				}
			} else {
				child = &gNode{
					id:     id,
					t:      node.t + distance,
					parent: node,
				}
				nodeMap[id] = child
				node.child = append(node.child, child)
				dfs(child)
			}
		}
	}

	dfs(rootNode)
	if len(nodeMap) < n {
		return -1
	}
	var dfs_longest_path func(node *gNode)
	var ans = 0
	dfs_longest_path = func(node *gNode) {
		if node == nil {
			return
		}
		if node.t > ans {
			ans = node.t
		}
		for _, c := range node.child {
			dfs_longest_path(c)
		}
	}
	dfs_longest_path(rootNode)
	return ans

}
